import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        /**
         * 二叉树的锯齿形层序遍历（先左往右，再从右往左）
         * 解题思路：
         *  正常的BFS层序遍历基础上，添加变量记录层次*/
        // 1 预处理
        List<List<Integer>> retArray = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 2 遍历
        // -记录层次，单数层从左往右，双数层从右往左
        int level = 1;
        while(!queue.isEmpty()) {
            // -1 记录层次个数
            int n = queue.size();
            List<Integer> tempArray = new LinkedList<>();

            // -2 出队
            for(int i = 0; i < n; i++) {
                TreeNode cur = queue.poll();
                if(cur == null) {
                    continue;
                }
                tempArray.add(cur.val);
                // -默认从左到右插入
                queue.offer(cur.left);
                queue.offer(cur.right);
            }

            // -3 整合数据（由于默认是从左到右，故当遍历至偶数层时，反转数据即可）
            if(level++ % 2 == 0) {
                Collections.reverse(tempArray);
            }
            if(!tempArray.isEmpty()) {
                retArray.add(tempArray);
            }
        }

        // 3 返回值
        return retArray;
    }
}
